﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SearchingAlgorithms
{
    class Program
    {
        static void Main(string[] args)
        {
            MyList<int> ll = new MyList<int> { 5, 8, 2, 7 };
            //MyList<int> ll = new MyList<int> { 85, 24, 63, 45, 17, 31, 96, 50 };
            //MyList<int> ll = new MyList<int> {1};
            //MyList<int> ll = new MyList<int> { 1, 17, 33, 46, 81, 243, 333, 454, 546, 765, 888, 978, 991, 998, 999, 18, 56, 1};
            //ll.SelectionSort();
            ll.BubbleSort();
            foreach (int i in ll)
                Console.Write(i + " ");
            int m = ll.MyBinarySearch(8);
            Console.WriteLine("Index: " + m);
            Console.ReadKey();
        }
    }

    public class MyList<T> : List<int>, ISearchBroker, ISortBroker
    {
        public int MyBinarySearch(int input)
        {
            return SearchBinary(0, this.Count - 1, input);
        }        

        private int SearchBinary(int start, int end, int input)
        {            
            int mid = (end + start) / 2;

            if (input == this[mid])
                return mid;

            else if (input > this[mid] && input <= this[end])
                return SearchBinary(mid + 1, end, input);

            else if (input >= this[start] && input < this[mid])
                return SearchBinary(start, mid - 1, input);
            return -1;
        }

        public void BubbleSort()
        {
            for (int i = 0; i < this.Count; i++)
            {
                for (int j = 0; j < this.Count - i - 1; j++)
                {
                    if (this[j] > this[j + 1])
                    {
                        int temp = this[j];
                        this[j] = this[j + 1];
                        this[j + 1] = temp;
                    }
                }
            }
        }

        public void SelectionSort()
        {
            for (int i = 0; i < this.Count - 1; i++)
            {
                for (int j = i + 1; j < this.Count; j++)
                {
                    if (this[i] > this[j])
                    {
                        int temp = this[i];
                        this[i] = this[j];
                        this[j] = temp;
                    }
                }
            }
        }

        public void InsertionSort()
        {
            for (int i = 1; i < this.Count; i++)
            {
                for (int j = 0; j < i; j++)
                {
                    if (this[i] < this[j])
                    {
                        int k = i;
                        int temp = this[i];
                        while (k > j)
                        {
                            this[k] = this[k - 1];
                            k--;
                        }
                        this[j] = temp;
                    }
                }
            }
        }

        public void MergeSort()
        {
            Merge(0, this.Count - 1);
        }

        private void Merge(int start, int end)
        {
            int i, j;
            List<int> A = new List<int>();
            List<int> B = new List<int>();

            int mid = (start + end) / 2;
            if (start == end) return;

            Merge(start, mid);
            Merge(mid + 1, end);

            for (i = start; i <= mid; i++)
                A.Add(this[i]);
            for (i = mid + 1; i <= end; i++)
                B.Add(this[i]);
            i = j =0;

            while (i < A.Count && j < B.Count)
            {
                if (A[i] < B[j])
                {
                    this[start + i + j] = A[i];
                    i++;
                }
                else
                {
                    this[start + i + j] = B[j];
                    j++;
                }
            }
                if (j == B.Count)
                {
                    for (int k = i; k < A.Count; k++)
                        this[start + j + k] = A[k];
                }
                if (i == A.Count)
                {
                    for (int k = j; k < B.Count; k++)
                        this[start + i + k] = B[k];
                }            
        }

        public void QuickSort()
        {
            QSort(0, this.Count - 1);            
        }

        private void QSort(int start, int pivot)
        {
            if (start >= pivot) return;

            int i = start;
            int j = pivot;
            while (true)
            {
                while (this[i] <= this[pivot])
                {
                    if(i >= j) break;
                    i++;
                }
                while (this[j] >= this[pivot]) 
                {
                    if(j <= i) break;
                    j--; 
                }

                if(i != j)
                    Swap(i, j);

                if (i >= j)
                {
                    if(i!= pivot)
                        Swap(i, pivot);
                    break;
                }
            }

            QSort(start, i - 1);
            QSort(i + 1, pivot);
        }

        private void Swap(int p, int q)
        {
            int temp = this[p];
            this[p] = this[q];
            this[q] = temp;
        }
    }

    interface ISearchBroker
    {
        int MyBinarySearch(int input);
    }

    interface ISortBroker
    {
        void SelectionSort();
        void BubbleSort();
        void InsertionSort();
        void MergeSort();
        void QuickSort();
    }
}
